package com.gaogzhen.algorithm.sort;

public class Quick {
    // 比较a是否大于b
    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    // 交换元素
    public static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //
    public static int partition(Comparable[] a, int lo, int hi) {
        // 初始化左右指针
        int left = lo, right = hi + 1;
        Comparable key = a[left];
        while (true) {
            // 右指针右往左查找小鱼分界值的数
            while (compare(a[--right], key)) {
                if (right == lo) {
                    break;
                }
            }
            // 左指针左往右查找大于分界值的数
            while (compare(key, a[++left])) {
                if (left == hi) {
                    break;
                }
            }
            // 比较左右指针
            if (left >= right) {
                break;
            }

            exch(a, left, right);

            // 如果左指针大于等于右指针，结束循环
            // 否则，交互左右指针指向的值
        }
        exch(a, right, lo);
        return right;
    }

    //  对数组a从索引lo->hi排序
    public static void sort(Comparable[] a, int lo, int hi) {
        // 递归校验
        if (lo >= hi) {
            return;
        }
        // 对数组索引lo->hi分组
        int partition = partition(a, lo, hi);
        // 左子数组排序
        sort(a, lo, partition - 1);
        // 右子数组排序
        sort(a, partition + 1, hi);
    }

    // 排序
    public static void sort(Comparable[] a) {
        // 1、初始化lo, hi
        int lo = 0, hi = a.length - 1;
        // 2、对数组a从索引lo->hi排序
        sort(a, lo, hi);
    }

}
